package puzzle.projecteuler.p100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Problem023 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Integer[] abundants = getAbundantNumbersUnder(28123);
		long s = 0;
		for (int i = 1; i < 28123; i ++) {
			if (!isSumOfTwoAbundants(abundants, i)) {
				s += i;
			}
		}
		System.out.println(s);
	}

	public static int d(int n) {
		int s = 0;
		for (int i = 1; i < n; i ++) {
			if (n%i==0) {
				s += i;
			}
		}
		return s;
	}
	
	public static Integer[] getAbundantNumbersUnder(int upper) {
		
		List<Integer> tmp = new ArrayList<Integer>();
		for (int i = 1; i < upper; i ++) {
			if (d(i) > i) {
				tmp.add(i);
			}
		}
		return tmp.toArray(new Integer[tmp.size()]);
	}
	
	public static boolean isSumOfTwoAbundants(Integer[] abundants, int num) {
		
		for (int i = 0; i < abundants.length; i ++) {
			if (num <= abundants[i]) {
				return false;
			} else {
				int left = num - abundants[i];
				if (Arrays.binarySearch(abundants, left) > -1) {
					return true;
				} else {
					continue;
				}
			}
		}
		return false;
	}
}
